package 我的Java学习_算法基础.day_06;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class _101_POJ_1006 {
    public static void main(String[] args) throws Exception{
        Scanner sc = new Scanner(System.in);
        int t = 1;
        List<long[]> aList = new ArrayList<long[]>();
        List<Long> dList = new ArrayList<Long>();
        while(sc.hasNext()){
            long[] a ={sc.nextLong(),sc.nextLong(),sc.nextLong()};
            long d = sc.nextInt();
            if(a[0]==-1&&a[1]==-1&&a[2]==-1&&d==-1) break;
            else {
                aList.add(a);
                dList.add(d);
            }
        }
        for(int i =0;i<aList.size();i++){
            long[] a = aList.get(i);
            long d = dList.get(i);
            long[] m = {23,28,33};
            long res = Line.linearEquationGroup(a,m);
            while(res<=d){
                res+=21252;
            }
            System.out.println("Case "+(t++)+": the next triple peak occurs in "+(res-d)+" days.");
        }

    }
    private static class Line {
        static long x;
        static long y;
        public static long gcd(long m,long n){
            return n==0?m:gcd(n,m%n);
        }
        /**
         * 最小公倍数 lowest common multiple
         */
        public static long lcm(long a,long b){
            return a*b/gcd(a,b);
        }

        /**
         * 扩展欧几里得
         * 调用完成后x、y是ax+by=gcd(a,b)的解
         * @param a
         * @param b
         * @return 最大公约数
         */
        public static long ext_gcd(long a,long b){
            if(b==0){
                x=1;
                y=0;
                return a;
            }
            long res = ext_gcd(b,a%b);
            //x,y已经被下一层递归更新了
            long x1 = x;//备份x
            x=y;//更新x
            y=x1-a/b*y;//更新y
            return res;
        }

        /**
         * 求ax+by=m 的解
         * @param a
         * @param b
         * @param m
         * @throws Exception
         */
        public static long linearEquation(long a,long b,long m)throws Exception{
            long d = ext_gcd(a,b);
            //m不是gcd（a,b）的倍数，这个方程无解
            if(m%d!=0) throw new Exception("无解");
            long n = m/d;
            x*=n;
            y*=n;
            return d;
        }
        /**
         * 求逆元
         * ax%n=1中的x
         * @param a
         * @param mo
         * @return
         * @throws Exception
         */
        public static long inverseElement(long a,long mo) throws Exception{
            long d = linearEquation(a,mo,1);
            x=(x%mo+mo)%mo;//保证x>0
            return d;
        }
        /**
         * x=a1(%m1)
         *  =a2(%m2)
         *  =a3(%m3)
         *  x=a1+m1y1   (1)
         *  x=a2+m2y2
         *  ==>m1y1+m2y2=a2-a1是一个线性方程
         *  可解出y1 linearEquation(m1,-m2,a2-a1)
         *  带回（1），得到特解x0 = a1+m1*y1--->x=x0+k*lcm(m1,m2)
         *  得到一个新方程 x = x0(mod lcm(m1,m2))
         */

        /**
         *
         * @param a 余数的数组
         * @param m 模的数组
         * @return  方程组的解
         * @throws Exception
         */
        public static long linearEquationGroup(long[] a,long[] m)throws Exception{
            int len = a.length;
            if(len==0&&a[0]==0) return m[0];
            for(int i =1;i<len;i++) {
                //这里往前看是两个方程
                long a2_a1 = a[i] - a[i - 1];
                long d = linearEquation(m[i - 1], -m[i], a2_a1);
                //现在的x是y1,用y1求得一个特解
                long x0 = a[i - 1] + m[i - 1] * x;
                long lcm = m[i - 1] * m[i] / d;
                a[i] = (x0 % lcm + lcm) % lcm;
                m[i] = lcm;
            }
            //合并完成后，只有一个方程：x = a[len-1](%m[len-1])
            return a[len-1]%m[len-1];
        }
    }


}
